1. Field of the Invention
The present invention relates to database construction and maintenance within object-oriented programming paradigms. More specifically, the invention relates to a method and apparatus for building and maintaining an object-oriented database of geospatial data for use with the development and maintenance of topological maps consistent with the Vector Product Format, Raster Product Format, and Text Product Standard developed for use by the U.S. Defense Mapping Agency, now known as the National Imagery and Mapping Agency.
2. Description of the Related Art
The use of maps and geographical characteristics has expanded well beyond the navigator, the cartographer, and the classroom the independent field of topology, which is the study of the characteristics, such as adjacency and contiguity, of geometrical objects that are independent of the underlying coordinate system. The primary purpose for providing topological information in contemporary geographic information systems is to expand spatial analysis capabilities. The National Imagery and Mapping Agency (NIMA) is one of many entities that require timely, relevant, and accurate imagery and geospatial information. NIMA maintains and disseminates databases of geographical data in three main formats: Vector Product Format (VPF), Raster Product Format (RPF), and Text Product Standard (TPS).
While the present invention is directed primarily toward VPF products, a brief introduction to the RPF and TPS formats is presented because the present invention provides for the first time a system that can incorporate into a single platform geospatial data structured in all three formats.
Raster Product Format (RPF) is defined in MIL-STD-2411, 2411-1, and 2411-2 and was developed to facilitate the interchange of raster data between producers and users of raster data by providing a standard database structure for arrays of pixel values. RPF is a standard data structure for geospatial databases composed of rectangular arrays of pixel values (e.g., digitized maps or images) in compressed or uncompressed form. Data in RPF form is intended to be used by application software on computer-readable interchange media, such as CD-ROM's, directly without further manipulations or transformation. RPF products include those generated from scanned charts, such as those stored in Compressed Arc Digitized Raster Graphics (CADGR), as well as SPOT imagery, such as Controlled Image Base (CIB). In general, RPF data is organized into frame and subframe files. Each frame file contains data for a specific geographical region, defined by a boundary expressed by four (4) latitude/longitude coordinates for a rectangular geographic area. Each frame file also includes a fixed number of data values decomposed into a matrix of subframes, representing color, value, or intensity of the corresponding point. Each product category that represents a single instantiation of RPF, or a family of instantiations of RPF, is described in a separate product specification.
Text Product Standard (TPS) is a textual format using Standard Group Mark-up Language (SGML). TPS provides digital textual information from NIMA hardcopy publications, such as the AMERICAN PRACTICAL NAVIGATOR and SAILING DIRECTIONS. Its information is basically in SGML format. For example, navigators can use TPS data to augment paper or digital charts with valuable information, including accurate directions.
Vector Product Format (VPF) is a standard U.S. Depart of Defense (DOD) format for vector-based digital map products and is defined by U.S. Military Specification MIL-STD-2407, DOD Interface Standard, Vector Product Format, 1996, which is incorporated herein by reference. NIMA, the primary mapping agency for the DOD, developed this standard and is producing an increasing number of digital products in this format. VPF is a standard relational format, structure, and organization for large geographic databases that is based on a georelational vector data model and is intended for direct access by application software. NIMA produces its vector digital map products in this format and offers VPFView as a software application that allows users to browse, display, and perform spatial queries on NIMA data in VPF. NIMA VPF products contain source data from maps, air photographs, satellite data, etc. Other software developers have developed a variety of applications to use and display NIMA-produced VPF data. For example, Environmental Systems Research Institute, Inc. (ESDI) has developed ArcInfo and ArcView to access this data, perform queries, and generally utilize the data within geographic information systems (GIS).
VPF represents a georelational framework based on a vector data model that is well suited to hold data for large geographic databases. Georelational digital vector data are connected points that represent natural and cultural geographic features. Various levels of spatial relationships can be represented in a vector data base such as the VPF data structure. A VPF database comprises three basic types of information for spatial features: spatial geometric properties (locations), non-spatial properties (attributes), and topological properties (relationships). This data is organized into a hierarchical structure of directories, tables, and indices. The root directory for a finite VPF database contains a number of library subdirectories, each representing a specific geographic region and scale. Within each library subdirectory are one or more coverage subdirectories, each representing a related group of feature classes. Each coverage subdirectory contains tables and indices describing its feature classes by attribute (non-spatial) and primitive (spatial) data. Feature data is further subdivided among tile subdirectories within each feature class. Each tile represents a spatial subregion within the library boundaries.
Referring now to FIG. 1, a typical prior art VPF data structure 100 is shown as a relational database with four hierarchical levels: a database level 10; a library level 12; a coverage level 14; and a feature level 16. Within these levels, VPF data is maintained in various types of relational database tables, which are stored as files. VPF tables are ASCII or binary files within the directories that are structured as one or more “columns”, or fields for different kinds of information, and many “rows” of records for each information type. Such tables are used to store feature, attribute, location, geometry, and topology information within the VPF structure. Indices are a special kind of table which have pointers to other tables and records.
At the top level of the VPF structure 100 is the database level 10, a logical collection of data managed as a unit. Each database will contain one or more libraries 11, which are generally organized along a geographic categorization, such as political units or latitude/longitude rectangles. An example of a library is the North American continent. Within each library, the data is organized into coverages 13, which represent features that are thematically and topologically related to each other. Boundaries, rivers, and transportation could all be examples of coverages are broken down into feature classes 15, each of which represents a homogeneous set of attributes. Transportation features could be roads, railroads, and airports. Feature classes 15 represent areas, lines, points, and/or text and consist of primitive data 17 and attribute data 18. Primitive data 17 describes the location, geometry, and topology of the features with coordinates, or topologically linked sets of nodes, edges, and faces. Attributes 18 are non-spatial data, modeling the thematic information about the features. Because both primitive 17 and attribute 18 information reside in the VPF data structure 100, both spatial (where) relationships and thematic (what) relationships can be modeled with VPF data. Spatial relationships, or topology, include adjacency, connectivity, intersection, containment, and composition.
FIG. 2 displays a block diagram of the hierarchical directory/file structure of the VPF data structure. A typical VPF product has a VPF database directory 20 containing pointers to each of the VPF libraries within each VPF database. Each library has a predefined geographic extent and source scale. Each library directory 22 has coverage subdirectories 24 where linked feature tables 26 store detailed information about thematically similar geospatial features (e.g., transportation, vegetation) and their attributes over the geographic extent of the library. Each feature table 26 includes primitives tables 28 and attributes tables 29. The information retained in these last two structures provide the physical representations of the geographical structures within each coverage level. The primitive tables 28 provide the location, geometry, and topology information of for each coverage level, using winged-edge topology in terms of areas, lines, points, and text. The attributes tables 29 provide physical characteristic information regarding each geographical structure within the coverage level. To facilitate faster access to primitive data, most VPF primitive tables 28 are tiled. Tiles are physical, as opposed to thematic, partitions of data of equal size utilized to break apart large blocks of data into manageable segments. Primitive tables 28 are stored in tile directories 27 within a VPF coverage. Under this structure, topology among VPF features is maintained only within each coverage.
The VPF software offered by NIMA is limited to simple map viewing. VPFView reads a VPF product database, produces user-defined views, and displays those views to the user. The user-built views can be saved to disk and subsequently reloaded for later viewing. While VPFView can be used to query the VPF database, it is limited to simple inquiries because VPFView was never designed to perform sophisticated GIS functions. Further, access to VPF data through non-NIMA software, such as ESDI's ArcView, often requires prior translation of the VPF database, a process both time-consuming and subsequently restrictive to whatever version of the VPF database existed at the time of translation. Additionally, use of the VPF to dynamically analyze topological information is not possible with any VPF-compatible system presently available. For example, within VPF, a bridge has an existence attribute; i.e., the bridge exists. If the user desires to view and analyze geospatial information in the absence of the bridge, the underlying relational VPF database must first be modified to change the existence attribute for this particular feature—a complex and time-consuming process that requires the updating of all related tables and files.
The VPF structure is known as a “relational” structure, because pointers and links join, or relate, the various primitives tables 28 and attributes tables 29 within each coverage level. Without this “relational” structure, the data would contain nothing more than simple geometry of the coverage features and not also their topology. This relationship makes VPF products attractive to users of geographic information systems, where spatial analysis is important.
VPF data is stored according to the structure defined in MIL-STD-2407. The Standard specifies the structure for directories, tables, table columns, table join relationships, and media exchange conventions for all VPF data. The data structure itself can be thought of as a template or skeleton within which the geospatial features and metadata are stored. While this standard describes the structure, it does not describe the contents of a set of VPF data; this is the role of a VPF product specification. A product specification corresponding to a specific database product stipulates the precise contents of feature tables and their relationships in the database. In this context, each separate product is defined by a product specification implemented with a VPF structure. Just as different types and scales of maps may be created for a geographic area, each designed for a different use, there are several types of VPF products with differing levels of feature content and density. Each official VPF product is defined by a different military specification describing the particular VPF structure to be utilized. Specification information includes which features, attributes, and attribute values will be allowed in the product as well as how the features will be grouped into coverages and what tiling scheme, if any, will be used. Currently, there are several VPF products being produced by NIMA.
In geographic applications, topology refers to any geographic relationship between connected geometric primitives that is not altered by continuous transformation. VPF recognizes four levels of topology:                Level 0—boundary representation, containing no explicit topological information, for manipulating purely geometric aspects of the spatial data;        Level 1—non-planar graph, suitable for representing networks;        Level 2—planar graph, in which no edges overlap; and        Level 3—full topology, in which no faces overlap.        
Level 3 is the most complex topological structure to manage in VPF databases, and winged-edge topology is the format that has been selected for representing level 3 coverages within the VPF database. The function of winged-edge topology is to provide line network and face, topology. Three components are necessary to define winged-edge topology: node information, edge information, and face information. An edge knows its neighboring edges by its right edge and left edge attributes. An edge, together with its left and right edges, gives a ‘winged’ appearance, leading to the term “winged-edge” topology. Referring now to FIG. 3, an edge 30 has a start node 31, which is connected to the left edge 32, and an end node 33, which is connected to the right edge 34. A neighboring edge 35 is any edge that shares a start node 31 or end node 33 with the original edge 30. Nodes provide contiguity information; for example, each edge 30 knows its start node 31 and end node 33. Start and end nodes also provide orientation information for edges, and define the common point for contiguous edges.
Adjacency information is also maintained by edges. An edge 30 knows its neighboring edges 35 by its right edge 34 and left edge 32 attributes. An edge 30, together with its left 32 and right 34 edges, gives a ‘winged’ appearance, leading to the term winged-edge topology. The right edge 34 is the first edge connected to the end node 33 in a counterclockwise direction. The left edge 32 is the first edge connected to the start node 31 in a counterclockwise direction. If there is no neighboring edge 35, the right 34 or the left 32 edge will exist by itself. Each edge also knows its left and right faces, 35 and 36, respectfully. Left 35 and right 36 faces are determined by the edge direction. With these definitions, winged-edge topology provides adjacency, contiguity, and the orientation of neighboring nodes, edges, and faces.
Due to the above rules for level 3 topology, any single line feature may consist of multiple edges; and any single node, edge, or face primitive could be used by more than one feature. Therefore, great care must be taken to maintain the correct linkages between the features and primitives. These complexities place a heavy burden on the maintenance of topological relationships following changes in feature data, especially in a relational database such as the VPF database. With a complex relational database model such as the vector product format, the coverage, features, and topological data resides in many tables that must be queried for every request for information from the database. Furthermore, because of the number of tables involved, maintaining referential integrity of the VPF database upon an update is very difficult. This difficulty arises because the VPF format relies on data residing within multiple specialized tables on multiple levels of the VPF relational database.
Although applications exist to view geospatial data in any of the VPF, RPF, and TPS data formats, no single software product exists to view, query, or manipulate all three formats on a one platform. Therefore, users must access separate programs to utilize data in each format. Cross-referencing data produced in different formats is difficult at best, thereby limiting the speed of assimilating the data and limiting the ability to query and display data from a variety of sources.
The present inventors have recognized that an object-oriented paradigm provides certain benefits for geographical databases. With an object-oriented data structure, topological and other spatial relationships reside in linked objects, and updates to the data can be handled more simply and directly. This is due to the object-oriented properties of identity, encapsulation, inheritance, and polymorphism. The preferred embodiments of the present invention overcome the problems associated with existing mechanisms for querying, updating, and translating VPF data by providing a geospatial information distribution system that permits easy and complete updating of VPF data, more complex queries of VPF data, and direct exporting of VPF data into a relational database structure. The present invention also permits easy use of data of differing formats and structures within an integrated geospatial information system. In particular, the invention incorporates existing data in VPF, RPF, and TPS files onto a single, object-oriented platform for GIS inquiry.